Maratones competidas/Maratón Nacional 2011/workspace/c/c4.cpp

   1 // Equipo Poncho, Carriel y Ruana
   2 using namespace std;
   3 #include <algorithm>
   4 #include <iostream>
   5 #include <iterator>
   6 #include <sstream>
   7 #include <fstream>
   8 #include <cassert>
   9 #include <climits>
  10 #include <cstdlib>
  11 #include <cstring>
  12 #include <string>
  13 #include <cstdio>
  14 #include <vector>
  15 #include <cmath>
  16 #include <queue>
  17 #include <stack>
  18 #include <list>
  19 #include <map>
  20 #include <set>
  21
  22 template <class T> string toStr(const T &x)
  23 { stringstream s; s << x; return s.str(); }
  24 template <class T> int toInt(const T &x)
  25 { stringstream s; s << x; int r; s >> r; return r; }
  26
  27 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  28 #define foreach(x, v) for (typeof (v).begin() x = (v).begin(); x != (v).end(); ++x)
  29 #define D(x) cout << #x " = " << (x) << endl;
  30
  31 const double EPS = 1e-9;
  32
  33 int cmp(double x, double y = 0, double tol = EPS) {
  34     return (x <= y + tol) ? (x + tol < y) ? -1 : 0 : 1;
  35 }
  36
  37 #define INPUT_FILE "compression"
  38
  39 const int MAXBASES = 105, oo = 1 << 28;
  40 int bases[MAXBASES];
  41
  42 int B, D;
  43 int bit[20]; // bit[i] = index of term i in the document
  44
  45 int dp[MAXBASES][1 << 16];
  46
  47 int docSize;
  48
  49 void binary(int x){
  50     for (int i = 0; i < 16; ++i){
  51         printf("%d", !!(x & (1 << i)));
  52     }
  53 }
  54
  55 void precompute(){
  56     for (int mask = 0; mask < (1 << 16); ++mask) {
  57         dp[B][mask] = oo;
  58     }
  59     dp[B][0] = 0;
  60
  61     for (int b = B - 1; b >= 0; --b) {
  62         for (int mask = 0; mask < (1 << 16); ++mask) {
  63             dp[b][mask] = dp[b+1][mask];
  64             if ((bases[b] | mask) != mask) {
  65                 if (mask < 1024) {
  66                     if (mask == 607) {
  67                         printf("Descartando mask "); binary(mask); printf(" porque no es compatible con bases[b=%d]", b); binary(bases[b]); puts("");
  68                        printf("bases[b] | mask = "); binary(bases[b] | mask);  puts("");
  69                     }
  70                 }
  71                 continue;
  72             }
  73             dp[b][mask] = min(dp[b][mask], dp[b+1][mask - bases[b]] + 1);
  74         }
  75     }
  76
  77     for (int b = B - 1; b >= 0; --b) {
  78         for (int mask = 0; mask < (1 << 16); ++mask) {
  79             if (dp[b][mask] < oo) {
  80                 printf("dp[%d][", b); binary(mask); printf("] = %d\n", dp[b][mask]);
  81             }
  82         }
  83     }
  84 }
  85
  86 void solve(int doc) {
  87
  88     //For(i, 0, B) if (compatible(bases[i])) printf("Base i=%d: %d\n", i, maskOfBase(bases[i]));
  89
  90   //  for (int i = 0; i < 16; ++i) {
  91 //        printf("bit[%d] = %d\n", i, bit[i]);
  92 //    }
  93
  94     int ans = dp[0][doc];
  95     //if (ans >= oo) ans = 0;
  96     printf("%d", ans);
  97 }
  98
  99 int main(){
 100     freopen(INPUT_FILE ".in", "r", stdin);
 101     while (cin >> B >> D) {
 102         if (B == 0 and D == 0) break;
 103         for (int i = 0; i < B; ++i) {
 104             bases[i] = 0;
 105
 106             int k; cin >> k;
 107             while (k--) {
 108                 int x; cin >> x; x--;
 109                 bases[i] |= (1 << x);
 110             }
 111             //printf("base[i=%d] = %d\n", i, bases[i]);
 112         }
 113         precompute();
 114         for (int j = 0; j < D; ++j) {
 115             int doc = 0;
 116             cin >> docSize;
 117             int k = docSize;
 118             while (k--) {
 119                 int x; cin >> x; x--;
 120                 doc |= (1 << x);
 121             }
 122             //printf("doc = %d\n", doc);
 123             solve(doc);
 124             if (j + 1 < D) printf(" ");
 125         }
 126         puts("");
 127
 128     }
 129     return 0;
 130
 131 }